package com.xxy.tree;

import sun.awt.windows.ThemeReader;

import java.math.BigDecimal;

/**
 * @author xxy
 * @create 2021 1 23 13:53
 * 二叉树的前中后序遍历步骤
 * 1.前序遍历
 * 1.1先输出当前节点
 * 1.2如果左子节点不为空，即递归继续前序遍历
 * 1.3如果右子节点不为空，即递归继续前序遍历
 *
 * 中序遍历和后续遍历也就一样了，只是左子节点和右子节点的顺序不同。
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        //二叉树所需要的节点
        HeroNode node1 = new HeroNode(1,"宋江");
        HeroNode node2 = new HeroNode(2,"吴用");
        HeroNode node3 = new HeroNode(3,"卢俊义");
        HeroNode node4 = new HeroNode(4,"林冲");
        HeroNode node5 = new HeroNode(5,"关胜");
        //手动创建一个二叉树
        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        binaryTree.setRoot(node1);
        //测试代码
      /*  System.out.println("前序遍历：");
        binaryTree.preOrder();
        System.out.println("中序遍历：");
        binaryTree.midOrder();
        System.out.println("后序遍历：");
        binaryTree.postOrder();
        //-----------查找---------------------//
        System.out.println("前序查找");
       HeroNode node = binaryTree.preOrderSearch(5);
        if(node!=null){
            System.out.println(node);
        }else{
            System.out.println("没有该节点！");
        }
        System.out.println("中序查找");
        HeroNode midNode = binaryTree.midOrderSearch(3);
        if(midNode!=null){
            System.out.println(midNode);
        }else{
            System.out.println("没有该节点！");
        }
        System.out.println("后序查找！");
        HeroNode postNode = binaryTree.postOrderSearch(5);
        if(postNode!=null){
            System.out.println(postNode);
        }else{
            System.out.println("没有该节点！");
        }*/
        System.out.println("删除前，前序遍历的结果：");
        binaryTree.preOrder();
        binaryTree.delNode(5);
        System.out.println("删除5节点后，前序遍历");
        binaryTree.preOrder();
    }
}
//创建一棵二叉树
class BinaryTree{
    private HeroNode root;//根节点
    public void setRoot(HeroNode root) {
        this.root = root;
    }
    //前序遍历
    public  void preOrder(){
        if(this.root!=null){
            this.root.preOrder();
        }else {
            System.out.println("当前二叉树为空");
        }
    }
    //中序遍历
    public void midOrder(){
        if(this.root!=null){
            this.root.midOrder();
        }else {
            System.out.println("当前二叉树为空！");
        }
    }
    //后序遍历
    public void postOrder(){
        if(this.root!=null){
            this.root.postOrder();
        }else {
            System.out.println("当前二叉树为空！");
        }
    }
    //前序查找
    public HeroNode preOrderSearch(int no){
        if(this.root!=null){
            return this.root.preOrderSearch(no);
        }else{
            return null;
        }
    }
    //中序查找
    public HeroNode midOrderSearch(int no){
        if(this.root!=null){
            return this.root.midOrderSearch(no);
        }else{
            return null;
        }
    }
    // 后序查找
    public HeroNode postOrderSearch(int no){
        if(this.root!=null){
            return this.root.postOrderSearch(no);
        }else{
            return null;
        }
    }
    //删除节点
    public void delNode(int no){
        if(root!=null){
            if(root.getNumber()==no){
                root=null;
            }else {
                root.delNode(no);
            }
        }else{
            System.out.println("空树！");
        }
    }
}
//heroNode节点
class HeroNode{
    private int number;
    private String name;
    private HeroNode left;//左节点
    private HeroNode right;//右节点
    public HeroNode(int number,String name){
        this.name=name;
        this.number = number;
    }
    //提供get和set方法

    public int getNumber() {
        return number;
    }

    public void setNumber(int number) {
        this.number = number;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "number=" + number +
                ", name='" + name + '\'' +
                '}';
    }
    //删除节点
    /*
        1.因为我们的二叉树是单向的，所以我们是判断当前节点的子节点是否为需要
        删除的节点，而不是判断当前节点。
     */
    public  void delNode(int no){
        if(this.left!=null&&this.left.number==no){
            this.left=null;
            return;
        }
        if(this.right!=null&&this.right.number==no){
            this.right=null;
            return;
        }
        if(this.left!=null){
            this.left.delNode(no);
        }
        if(this.right!=null){
            this.right.delNode(no);
        }
    }
    //前序遍历
    public void preOrder(){
        //输出当前节点
        System.out.println(this);
        //左子树
        if(this.left!=null){
            this.left.preOrder();
        }
        //左子树遍历结束，回到了根节点，然后开始右节点
        if(this.right!=null){
            this.right.preOrder();
        }
        //结束
    }
    //中序遍历
    public void midOrder(){
        //首先遍历左子树
        if(this.left!=null){
            this.left.midOrder();
        }
        //输出父节点
        System.out.println(this);
        //遍历右节点
        if(this.right!=null){
            this.right.midOrder();
        }
        //结束
    }
    //后序遍历
    public void postOrder(){
        //先遍历左子树
        if(this.left!=null){
            this.left.preOrder();
        }
        //遍历右子树
        if(this.right!=null){
            this.right.postOrder();
        }
        //输出节点
        System.out.println(this);
    }
    //前序查找
   public HeroNode preOrderSearch(int no){
        if(this.number ==no){
            return this;
        }
        //进行左子树
       HeroNode resNode =null;
       if (this.left != null){
           resNode = this.left.preOrderSearch(no);
       }
       if(resNode!=null){
           return resNode;
       }
       //右子树
       if(this.right!=null){
           resNode = this.right.preOrderSearch(no);
       }
           return resNode;
   }
   //中序查找
    public HeroNode midOrderSearch(int no){
        //进行左子树
        HeroNode resNode =null;
        if (this.left != null){
            resNode = this.left.preOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        if(this.number ==no){
            return this;
        }
        //右子树
        if(this.right!=null){
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }
    //后序查找
    public HeroNode postOrderSearch(int no) {
        //进行左子树
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //右子树
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        System.out.println("进入后序查找~");
        if (this.number == no) {
            return this;
        }
        return null;
    }
}
//106